package com.tgy.programmer_code_interview_guide._01_stack_queue;

import java.util.Deque;
import java.util.LinkedList;

public class _09_最大值减最小值小于等于num的子数组数量_deque {

    public static int maxSubArray(int[] nums, int k) {

        Deque<Integer> decrementDeque = new LinkedList<>();
        Deque<Integer> incrementDeque = new LinkedList<>();

        int count = 0;
        int left = 0, right = 0;
        int len = nums.length;
        while (left < len) {

            // 寻找以left为起点的连续数组最远right
            while (right < len) {

                while (!decrementDeque.isEmpty() && decrementDeque.getLast() < nums[right]) {

                    decrementDeque.removeLast();
                }

                while (!incrementDeque.isEmpty() && incrementDeque.getLast() > nums[right]) {

                    incrementDeque.removeLast();
                }

                decrementDeque.addLast(nums[right]);
                incrementDeque.addLast(nums[right]);
                if (decrementDeque.getFirst() - incrementDeque.getFirst() > k) {

                    break;
                }

                right++;
            }

            if (decrementDeque.getFirst() == nums[left]) {

                decrementDeque.removeFirst();
            }

            if (incrementDeque.getFirst() == nums[left]) {

                incrementDeque.removeFirst();
            }

            count += (right - left);

            left++;
        }

        return count;
    }

    public static void main(String[] args) {

        /**
         * 1,2,3
         *  1/1-2/1-2-3
         *  2,3,4
         *  2/2-3/2-3-4
         */
        int result = maxSubArray(new int[]{1, 2, 3, 4, 5}, 2);
        System.out.println(result);
    }
}
